package com.yitiao.data_algorithms.structure.linked;

import lombok.Data;

/**
 * 真正动态的数据结构,丧失了随机访问的能力
 * 深入的理解引用和指针
 * 深入理解递归
 * 辅助其它数据结构
 * 数据存储在节点【Node】中
 * 每个节点是一个车厢，存放元素和下一个车厢的地址
 *
 * 虚拟头结点 dummyHead.next=head
 *
 * - 基本操作
 *   - 链表实现栈 链表头作为栈顶，因其
 *   - 链表实现队列 尾指针
 * - 链表与递归
 *   -
 */
public class LinkedList<E> {
    // 私有化，不暴露给用户
    private class Node{
        public Node next;
        public E e;

        // 三类构造方法
        public Node(Node node, E e) {
            this.next = node;
            this.e = e;
        }
        public Node(Node node) {
            this.next = node;
        }
        public Node(E e) {
            this.e = e;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "next=" + next +
                    ", e=" + e +
                    '}';
        }
    }

    private Node head;
    private Node dummyNode=new Node(head);
    private int size;

    public int getSize(){
        return this.size;
    }

    public boolean isEmpty(){
        return size==0;
    }
    // 新增 删除 遍历

    /**
     * 头插法
     */
    public void addFirst(E e){
//        // 复制一个头结点
//        Node h=head;
//        // 创建新结点
//        Node newNode = new Node(e);
//        // 下一个结点的地址指向头结点
//        newNode.next=h;
//        // 新插入的结点作为新的头结点
//        head=newNode;

        // 一行
        head = new Node(head, e);
        // 容量+1
        size++;
    }

    /**
     * 尾插法
     */
    public void addLast(E e){
        addIndex(size,e);
    }

    /**
     *插入指定位置
     * 关键在于找到前一个node.next
     * node.next=prev.next
     * prev.next=node
     */
    public void addIndex(int index,E e){
        // 参数校验
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("Parameter is not valid");
        }
        if (index==0){
            addFirst(e);
        }
        // 寻找prev
        Node prev = head;
        for (int i = 0; i < index-1; i++) {
            prev=prev.next;
        }
        // 简化写法
        prev.next= new Node(prev.next, e);

        size++;
    }

    /**
     * 获取元素
     *      按下标
     *      头元素
     *      尾元素
     */
    public E get(int index) {
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * 删除指定位置元素
     *      同样删除
     */
    public void remove(int index){
        // 虚拟头结点
        Node prev = dummyNode;
        // 如果为0，不进入循环，prev正好是dummyNode
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }

        Node delNode=prev.next;
        prev.next=delNode.next;
        delNode.next=null;   // 这步不要忘记

        size--;

    }

    public String getAll(){
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < this.size; i++) {
            builder.append(get(i)).append(" ");
        }
        return builder.toString();
    }
}
